# 动态规划
# https://leetcode-cn.com/problems/super-egg-drop/
# 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
#
# 已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
#
# 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋
# 扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
#
# 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

# 为什么要取值最大的查找次数？（最坏）
# 因为我们是要找无论 F 的初始值如何的条件下的查找次数，所以我们要在一号楼和二号楼各自的查找次数中选择那个最大的值

memo = dict()


def dp(k, n):
    # base case
    if k == 1:
        return n
    if n == 0:
        return 0
        # 避免重复计算
    if (k, n) in memo:
        return memo[(k, n)]
    res = float('INF')
    # 穷举所有可能的选择
    for i in range(1, n + 1):
        # 最坏情况下的最少扔鸡蛋次数
        res = min(res,
                  max(
                      dp(k - 1, i - 1),  # 碎
                      dp(k, n - i)  # 没碎
                  ) + 1  # 在第 i 楼扔了一次
                  )
    # 记入备忘录
    memo[(k, n)] = res
    return res


if __name__ == '__main__':
    print('start')
    print(dp(2, 100))
